package com.li.algorithm.leetcode.hot100;

public class Test17 {
//    public int firstMissingPositive(int[] nums) {
//        //TODO:排序（时间复杂度为O(n)的排序算法是不存在的）
//        int count = 1;
//        int pre = -1;
//        Arrays.sort(nums);
//        for (int num : nums) {
//            if (num <= 0 || num == pre) {
//                continue;
//            }
//            if (num != count) {
//                return count;
//            }
//            pre = num;
//            count++;
//        }
//        return count;
//    }


    /**
     * 方法2：原地哈希
     * 时间复杂度：O(N);空间复杂度：O(1)
     */
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] < len && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return len + 1;
    }
    public static void main(String[] args) {
        Test17 test17 = new Test17();
        System.out.println(test17.firstMissingPositive(new int[]{0,2,2,1,1}));
    }
}
